package algorithm.test;

public class RankKth {

	/**
	 * invokes this method to allow array containing duplicate elements
	 * 
	 * @param index
	 * @param direction
	 * @return
	 */
	private int moveBound(int index, String direction) {
		if (direction.equals("left")) {
			while (true) {
				if (index - 1 >= 0) {
					if (intArr[index] == intArr[index - 1])
						index--;
					else
						break;
				} else
					break;
			}
		} else {
			while (true) {
				if (index + 1 < intArr.length) {
					if (intArr[index] == intArr[index + 1])
						index++;
					else
						break;
				} else
					break;
			}
		}
		return index;
	}

	private int[] intArr;

	/**
	 * get the k'th element's value
	 * 
	 * @param intArr
	 * @return value of k'th element
	 */
	public int searchKthEle(int[] intArr, int k) {
		if (k < 0 || k > intArr.length - 1)
			return Integer.MAX_VALUE;
		this.intArr = intArr;
		int retIndex, head, rear;
		head = 0;
		rear = intArr.length - 1;
		retIndex = swapAccrodingToIndex(head, rear);
		for (;;) {
			if (retIndex == k || head >= rear)
				return intArr[retIndex];
			else if (retIndex < k) {
				head = retIndex + 1;
				head = moveBound(head, "right");
				retIndex = swapAccrodingToIndex(head, rear);
			} else {
				rear = retIndex - 1;
				rear = moveBound(rear, "left");
				retIndex = swapAccrodingToIndex(head, rear);
			}
		}
	}

	/**
	 * find out element's index in a array when the array is sorted.
	 * 
	 * @param intArr
	 *            a array sorted or not sorted
	 * @param element
	 *            a element in the array.
	 * @return index
	 */
	private int swapAccrodingToIndex(int head, int rear) {
		int index = (rear - head) / 2 + head;
		System.out.println(String.format("head=%d, rear=%d, index=%d", head, rear, index));
		disp();

		/*
		 * head=0, rear=1, index=0 1,2,2,35,3,3,5,61,324,513, index=1, value=2
		 * 1,2,2,35,3,3,5,61,324,513,
		 */
		int splitEle = intArr[index];
		int i, j;
		i = head;
		j = rear;
		while (i < j) {
			while (i < index) {
				if (intArr[i] > splitEle) {
					intArr[index] = intArr[i];
					index = i;
					break;
				}
				i++;
			}
			while (j > index) {
				if (intArr[j] < splitEle) {
					intArr[index] = intArr[j];
					index = j;
					break;
				}
				j--;
			}
		}
		intArr[index] = splitEle;

		System.out.println(String.format("index=%d, value=%d", index, intArr[index]));
		disp();
		System.out.println("=========");
		return index;// element's index in a sorted arr
	}

	private void disp() {
		for (int i = 0; i < intArr.length; i++) {
			System.out.print(intArr[i] + ",");
		}
		System.out.println();
	}
}
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
